﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Web;

namespace Automata.examen2
{
    class MultiplicacionMatrices
    {
        private long[,] matrizA;
        private long[,] matrizB;
        private long[,] matrizC;

        private long totalMultiplicaciones;
        private int N;

        /// <summary>
        /// Lee la matriz de contenido y la deja en matriz
        /// </summary>
        /// <param name="matriz">La matriz que se llenará</param>
        /// <param name="contenido">El contenido de la matriz</param>
        private void leeMatriz(long[,] matriz, string contenido)
        {
            string[] lineas = contenido.Split(new char[] { ';' });

            for (int i = 0; i < lineas.Length; i++)
            {
                string[] celdas = lineas[i].Split(new char[] { ' ' });

                for (int j = 0; j < lineas.Length; j++)
                    matriz[i, j] = Int64.Parse(celdas[j]);
            }

        }

        /// <summary>
        /// Carga las matrices del archivo en las viables matrizA y matrizB
        /// inicializa en 0 matrizC
        /// </summary>
        /// <param name="archivo">El stream del archivo donde se encuentran las matrices</param>
        private void cargaMatrices(Stream archivo)
        {
            string contenido = EntradaSalida.leeArchivo(archivo);

            string[] matrices = contenido.Split(new char[] { '.' });
            string[] lineas = matrices[0].Split(new char[] { ';' });

            N = lineas.Length;

            matrizA = new long[N, N];
            matrizB = new long[N, N];
            matrizC = new long[N, N];

            leeMatriz(matrizA, matrices[0]);
            leeMatriz(matrizB, matrices[1]);
        }

        /// <summary>
        /// Sube el archivo enviado como parámetro, multiplica las matrices
        /// utilizando el algoritmo seleccionado y devuelve el número de
        /// multiplicaciones que se hicieron en un formato amigable
        /// </summary>
        /// <param name="archivo">El stream del archivo donde se encuentran las matrices</param>
        /// <param name="algortimo">El algoritmo que se va a usar</param>
        /// <returns>El número de multiplicaciones que se hicieron</returns>
        public string multiplica(Stream archivo)
        {
            try
            {
                cargaMatrices(archivo);
            }
            catch (Exception)
            {
                return "El archivo no tiene el formato correcto";
            }

           return fuerzaBruta() + 
                  "<br /> <br />" + 
                  strassen();
        }

        /// <summary>
        /// Multiplica las matrices por fuerza bruta y devuelve el número de 
        /// multiplicaciones que se hicieron en formato amigable
        /// </summary>
        /// <returns></returns>
        private string fuerzaBruta()
        {
            try
            {
                totalMultiplicaciones = 0;

                for (int i = 0; i < N; i++)
                    for (int j = 0; j < N; j++)
                        for (int k = 0; k < N; k++)
                        {
                            if (matrizA[i, k] == 0 || matrizB[k, j] == 0)
                                continue;
                            matrizC[i, j] += matrizA[i, k] * matrizB[k, j];
                            totalMultiplicaciones++;
                        }

            }
            catch (Exception)
            {
                return "Las multiplicaciones hicieron que se desbordaran los números";
            }

            escribeMatrizSalida("matrizBruta.txt");

            return "Usando el algoritmo de fuerza bruta, se hicieron " + totalMultiplicaciones + " multiplicaciones. (Multiplicaciones por 0 no se cuentan)" +
                   "<br /> <br /> Click <a href=\"../files/matrizBruta.txt\" target=\"_blank\" > aquí </a> para bajar la matriz.";        
        }

        /// <summary>
        /// Calcula el exponencial de 2 igual o mayor a N más cercano
        /// </summary>
        /// <returns>El exponencial de 2 igual o mayor a N más cercano</returns>
        private int ExponencialDe2()
        {
            int prueba = 1;

            while (prueba < N)
                prueba *= 2;

            return prueba;
        }

        /// <summary>
        /// Suma las matrices matriz1 y matriz2 y las devuelve
        /// </summary>
        /// <param name="matriz1">La matriz1 a sumar</param>
        /// <param name="matriz2">La matriz2 a sumar</param>
        /// <param name="tamaño">El largo de la matriz</param>
        private long[,] sumaMatrices(long[,] matriz1, long[,] matriz2, int tamaño)
        {
            long[,] suma = new long[tamaño, tamaño];

            for (int i = 0; i < tamaño; i++)
                for (int j = 0; j < tamaño; j++)
                    suma[i, j] = matriz1[i, j] + matriz2[i, j];

            return suma;
        }

        /// <summary>
        /// Resta a la matriz matriz1 la matriz2 y la devuelve
        /// </summary>
        /// <param name="matriz1">La matriz1 a restar</param>
        /// <param name="matriz2">La matriz2 a restar</param>
        /// <param name="tamaño">El largo de la matriz</param>
        private long[,] restaMatrices(long[,] matriz1, long[,] matriz2, int tamaño)
        {
            long[,] suma = new long[tamaño, tamaño];

            for (int i = 0; i < tamaño; i++)
                for (int j = 0; j < tamaño; j++)
                    suma[i, j] = matriz1[i, j] - matriz2[i, j];

            return suma;
        }

        /// <summary>
        /// Devuelve una submatriz de la matriz enviada como parámetro.
        /// La submatriz será la que esté en el cuadrante enviado como parámetro
        /// </summary>
        /// <param name="matriz1">La matriz a fraccionar</param>
        /// <param name="tamaño">El tamaño de la matriz</param>
        /// <param name="cuadrante">El cuadrante a extraer de la matriz</param>
        /// <returns>El cuadrante de la matriz especificado</returns>
        private long[,] fraccionaMatriz(long[,] matriz1, int tamaño, Cuadrante cuadrante)
        {
            long[,] fraccion = new long[tamaño / 2, tamaño / 2];

            int iInicial = 0, iFinal = 0, jInicial = 0, jFinal = 0;

            switch (cuadrante)
            {
                case Cuadrante.SUPERIOR_IZQUIERDO:
                    iInicial = 0;
                    jInicial = 0;
                    iFinal = tamaño / 2;
                    jFinal = tamaño / 2;
                    break;
                case Cuadrante.SUPERIOR_DERECHO:
                    iInicial = tamaño / 2;
                    jInicial = 0;
                    iFinal = tamaño;
                    jFinal = tamaño / 2;
                    break;
                case Cuadrante.INFERIOR_IZQUIERDO:
                    iInicial = 0;
                    jInicial = tamaño / 2;
                    iFinal = tamaño / 2;
                    jFinal = tamaño;
                    break;
                case Cuadrante.INFERIOR_DERECHO:
                    iInicial = tamaño / 2;
                    jInicial = tamaño / 2;
                    iFinal = tamaño;
                    jFinal = tamaño;
                    break;
            }

            for (int i1 = 0, i2 = iInicial; i2 < iFinal; i1++, i2++)
                for (int j1 = 0, j2 = jInicial; j2 < jFinal; j1++, j2++)
                    fraccion[i1, j1] = matriz1[i2, j2];

            return fraccion;            
        }

        /// <summary>
        /// Toma las matrices en los cuatro cuadrantes y genera otra
        /// </summary>
        /// <param name="matriz11">La matriz en la esquina superior izquieda</param>
        /// <param name="matriz12">La matriz en la esquina superior derecha</param>
        /// <param name="matriz21">La matriz en la esquina inferior izquieda</param>
        /// <param name="matriz22">La matriz en la esquina inferior derecha</param>
        /// <param name="tamaño">El tamaño de la matriz final</param>
        /// <returns>La matriz unida</returns>
        private long[,] uneMatriz(long[,] matriz11, long[,] matriz12, long[,] matriz21, long[,] matriz22, int tamaño)
        {
            long[,] unida = new long[tamaño, tamaño];

            for (int i = 0; i < tamaño / 2; i++)
                for (int j = 0; j < tamaño / 2; j++)
                    unida[i, j] = matriz11[i, j];

            for (int i = 0, i1 = tamaño / 2; i < tamaño / 2; i++, i1++)
                for (int j = 0; j < tamaño / 2; j++)
                    unida[i1, j] = matriz12[i, j];

            for (int i = 0; i < tamaño / 2; i++)
                for (int j = 0, j1 = tamaño / 2; j < tamaño / 2; j++, j1++)
                    unida[i, j1] = matriz21[i, j];

            for (int i = 0, i1 = tamaño / 2; i < tamaño / 2; i++, i1++)
                for (int j = 0, j1 = tamaño / 2; j < tamaño / 2; j++, j1++)
                    unida[i1, j1] = matriz22[i, j];

            return unida;
        }

        /// <summary>
        /// Calcula recursivamente el método de Strassen para multiplicar matrices
        /// </summary>
        /// <param name="matriz1">La matriz1 a multiplicar</param>
        /// <param name="matriz2">La matriz2 a multiplicar</param>
        /// <param name="tamaño">El largo de la matriz</param>
        private long[,] strassen(long[,] matriz1, long[,] matriz2, int tamaño)
        {            
            //Caso base
            if (tamaño == 1)
            {
                long[,] res;

                res = new long[1, 1];

                if (matriz1[0, 0] == 0 || matriz2[0, 0] == 0)
                    return res;

                res[0, 0] = matriz1[0, 0] * matriz2[0, 0];
                totalMultiplicaciones++;
                return res;
            }

            //Cuadrantes

            long[,] A11 = fraccionaMatriz(matriz1, tamaño, Cuadrante.SUPERIOR_IZQUIERDO);
            long[,] A21 = fraccionaMatriz(matriz1, tamaño, Cuadrante.SUPERIOR_DERECHO);
            long[,] A12 = fraccionaMatriz(matriz1, tamaño, Cuadrante.INFERIOR_IZQUIERDO);
            long[,] A22 = fraccionaMatriz(matriz1, tamaño, Cuadrante.INFERIOR_DERECHO );
            long[,] B11 = fraccionaMatriz(matriz2, tamaño, Cuadrante.SUPERIOR_IZQUIERDO);
            long[,] B21 = fraccionaMatriz(matriz2, tamaño, Cuadrante.SUPERIOR_DERECHO);
            long[,] B12 = fraccionaMatriz(matriz2, tamaño, Cuadrante.INFERIOR_IZQUIERDO);
            long[,] B22 = fraccionaMatriz(matriz2, tamaño, Cuadrante.INFERIOR_DERECHO);

            //M's

            int tamaño2 = tamaño / 2;

            long[,] M1 = strassen(sumaMatrices(A11, A22, tamaño2), sumaMatrices(B11, B22, tamaño2), tamaño2);
            long[,] M2 = strassen(sumaMatrices(A21, A22, tamaño2), B11 , tamaño2);
            long[,] M3 = strassen(A11, restaMatrices(B12, B22, tamaño2), tamaño2);
            long[,] M4 = strassen(A22, restaMatrices(B21, B11, tamaño2), tamaño2);
            long[,] M5 = strassen(sumaMatrices(A11, A12, tamaño2), B22, tamaño2);
            long[,] M6 = strassen(restaMatrices(A21, A11, tamaño2), sumaMatrices(B11, B12, tamaño2), tamaño2);
            long[,] M7 = strassen(restaMatrices(A12, A22, tamaño2), sumaMatrices(B21, B22, tamaño2), tamaño2);

            //C's

            long[,] C1 = sumaMatrices(M1, sumaMatrices(M4, restaMatrices(M7, M5, tamaño2), tamaño2), tamaño2);
            long[,] C2 = sumaMatrices(M3, M5, tamaño2);
            long[,] C3 = sumaMatrices(M2, M4, tamaño2);
            long[,] C4 = sumaMatrices(M1, sumaMatrices(M3, restaMatrices(M6, M2, tamaño2), tamaño2), tamaño2); 

            return uneMatriz(C1, C3, C2, C4, tamaño);
        }

        /// <summary>
        /// Expande la matriz enviada como parámetro para que sea de tamaño 'grande'
        /// </summary>
        /// <param name="matriz">La matriz a expandir</param>
        /// <param name="grande">La dimension que se desea</param>
        /// <param name="original">El tamaño original de la matriz</param>
        /// <returns>La matriz expandida</returns>
        private long[,] incrementa(long[,] matriz, int grande, int original)
        {
            long[,] nueva = new long[grande, grande];

            for (int i = 0; i < original; i++)
                for (int j = 0; j < original; j++)
                    nueva[i, j] = matriz[i, j];

            return nueva;
        }

        /// <summary>
        /// Recorta la matriz enviada como parametro al valor anterior
        /// </summary>
        /// <param name="matriz">La matriz a recortar</param>
        /// <param name="anterior">La dimensión anterior (a recortar)</param>
        /// <param name="actual">Las dimensiones actuales</param>
        /// <rereturns>La matriz recortada</rereturns>
        private long[,] recortaMatriz(long[,] matriz, int anterior, int actual)
        {
            if (anterior == actual)
                return matriz;

            long[,] nueva = new long[anterior, anterior];

            for (int i = 0; i < anterior; i++)
                for (int j = 0; j < anterior; j++)
                    nueva[i, j] = matriz[i, j];

            N = anterior;

            return nueva;
        }

        /// <summary>
        /// Multiplica las matrices con strassen y devuelve el número de 
        /// multiplicaciones que se hicieron en formato amigable
        /// </summary>
        /// <returns></returns>
        private string strassen()
        {
            totalMultiplicaciones = 0;

            int grande = ExponencialDe2();
            int anterior = N;

            if (grande != N)                
            {
                matrizA = incrementa(matrizA, grande, N);
                matrizB = incrementa(matrizB, grande, N);
                anterior = N;                
                N = grande;             
            }

            matrizC = strassen(matrizA, matrizB, N);

            matrizC = recortaMatriz(matrizC, anterior, N);

            escribeMatrizSalida("matrizStrassen.txt");

            return "Usando el algoritmo de Strassen, se hicieron " + totalMultiplicaciones + " multiplicaciones. (Multiplicaciones por 0 no se cuentan)" +
                   "<br /> <br /> Click <a href=\"../files/matrizStrassen.txt\" target=\"_blank\" > aquí </a> para bajar la matriz.";        
        }

        /// <summary>
        /// En el archivo files/matrizSalida.txt se escribe la matriz
        /// </summary>
        /// <param name="archivo">El nombre del archivo a escribir</param>
        private void escribeMatrizSalida(string archivo)
        {
            string contenido = ""; 

            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    contenido += matrizC[i, j];

                    if ((j + 1) < N)
                        contenido += " ";
                }
                if ((i + 1) < N)
                    contenido += ";";
            }

            EntradaSalida.escribeArchivo(archivo, contenido);
        }
    }

    public enum Cuadrante
    {
        SUPERIOR_IZQUIERDO = 1,
        SUPERIOR_DERECHO,
        INFERIOR_IZQUIERDO,
        INFERIOR_DERECHO
    }

}